package leetcode_700;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *ReplaceWords_648 给定一个字典存放前缀 然后给定一个字符串  问字符串里的单词能否被字典里的前缀替换 如果能替换 用最短前缀替换
 *describe:用前缀树实现 用flag标记树终结 AC 81%
 *2018年9月26日 下午1:54:10
 */
public class ReplaceWords_648 {
	public static void main(String[] args) {
		ReplaceWords_648 test=new ReplaceWords_648();
		List<String> list=new ArrayList<String>();
		list.add("cat");
		list.add("bat");
		list.add("rat");
		System.out.println(test.replaceWords(list, "the cattle was rattled by the battery"));
	}
	
	class  PreTree{
		Character now;
		boolean flag;//表示这个是否是终结
		Map<Character,PreTree> map;
		public PreTree(Character now) {
			this.now=now;
		}
	}
	
	public String replaceWords(List<String> dict, String sentence) {
		PreTree[] trees=new PreTree[26];
        for(String str:dict) {//建立树的过程
        	char chars[]=str.toCharArray();
        	PreTree tree=trees[chars[0]-'a'];
        	if(tree==null) {//还没有收藏该树
        		tree=new PreTree(chars[0]);
        		trees[chars[0]-'a']=tree;
        	}
        	buildTree(tree,chars,1);
        }
        String[] words=sentence.split(" ");
        for(int i=0;i<words.length;++i) {
        	char chars[]=words[i].toCharArray();
        	PreTree tree=trees[chars[0]-'a'];
        	if(tree==null)
        		continue;
        	StringBuilder sb=new StringBuilder();
        	sb.append(chars[0]);
        	if(search(tree, chars, 1, sb)) {
        		words[i]=sb.toString();
        	}
        }
        StringBuilder res=new StringBuilder();
        for(String word:words) {
        	res.append(word).append(" ");
        }
        res.deleteCharAt(res.length()-1);
        return res.toString();
    }
	
	private void buildTree(PreTree tree,char[] chars,int index) {
		if(index==chars.length) {
			tree.flag=true;
			tree.map=null;//为了使每次返回最小前缀 那么剪切下面的后缀
			return ;
		}
		//那么为其建立前缀树索引
		if(tree.map==null) {
			tree.map=new HashMap<Character,PreTree>();
		}
		PreTree now=tree.map.get(chars[index]);
		if(now==null) {//没有这颗索引子树
			now=new PreTree(chars[index]);
			tree.map.put(chars[index], now);
		}
		if(now.flag==true)
			return ;//直接结束
		buildTree(now, chars, index+1);
	}
	
	private boolean search(PreTree tree,char[] chars,int index,StringBuilder sb) {
		if(tree.flag) {//这是终结树
			return true;
		}
		if(index==chars.length)
			return true;
		PreTree now=tree.map.get(chars[index]);	
		if(now==null)//前缀不匹配
			return false;
		sb.append(chars[index]);
		return search(now,chars,index+1,sb);
	}
}
